package com.shawn.algorithm.dynamicprogramming;

/**
 * 0-1 背包问题(最大重量，最大价值)
 */
public class ZeroOneValueBag {

	private int maxV = Integer.MIN_VALUE;
	/**
	 * 物品重量
	 */
	private int[] weight = {2, 2, 4, 6, 3};

	/**
	 * 物品价值
	 */
	private int[] value = {3, 4, 8, 9, 6};

	/**
	 * 物品数量
	 */
	private int n = 5;

	/**
	 * 背包最大承受重量
	 */
	private int w = 9;

	/**
	 * @param weight: 物品重量
	 * @param n：物品个数
	 * @param w：背包可承受重量
	 *
	 * @return
	 */
	public int knapsack(int[] weight, int[] value, int n, int w) {
		int[][] states = new int[n][w + 1];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < w + 1; ++j) {
				states[i][j] = -1;
			}
		}
		states[0][0] = 0;
		if (weight[0] <= w) {
			states[0][weight[0]] = value[0];
		}
		for (int i = 1; i < n; ++i) {
			for (int j = 0; j <= w; ++j) {
				if (states[i - 1][j] >= 0) {
					states[i][j] = states[i - 1][j];
				}
			}
			for (int j = 0; j <= w - weight[i]; ++j) {
				if (states[i - 1][j] >= 0) {
					int v = states[i - 1][j] + value[i];
					if (v > states[i][j + weight[i]]) {
						states[i][j + weight[i]] = v;
					}
				}
			}
		}
		// 找出最大值
		int maxvalue = -1;
		for (int j = 0; j <= w; ++j) {
			if (states[n - 1][j] > maxvalue) {
				maxvalue = states[n - 1][j];
			}
		}
		return maxvalue;
	}

	public int knapSack2(int[] wt, int[] val, int n, int W) {
		int i, w;
		//rv means return value
		int rv[][] = new int[n + 1][W + 1];

		// Build table rv[][] in bottom up manner
		for (i = 0; i <= n; i++) {
			for (w = 0; w <= W; w++) {
				if (i == 0 || w == 0) {
					rv[i][w] = 0;
				} else if (wt[i - 1] <= w) {
					rv[i][w] = Math.max(val[i - 1] + rv[i - 1][w - wt[i - 1]], rv[i - 1][w]);
				} else {
					rv[i][w] = rv[i - 1][w];
				}
			}
		}

		return rv[n][W];
	}

	public static void main(String[] args) {
		ZeroOneValueBag bag = new ZeroOneValueBag();
		System.out.println(bag.knapSack2(bag.weight, bag.value, bag.n, bag.w));
		System.out.println(bag.knapsack(bag.weight, bag.value, bag.n, bag.w));
	}
}
